1. Field of Invention
The present invention generally relates to coding devices, and particularly relates to a coding device which compresses an image through coding of the image.
2. Description of the Related Art
A recent diversification of data communication and data processing has created demands for facsimile devices having data-exchange functions and personal computers capable of treating black-and-white-multi-level images and color-multi-level images. The black-and-white-multi-level images are comprised of a plurality of bits assigned to each pixel, and the color-multi-level images are comprised of a plurality of color components, each of which is represented by a plurality of bits assigned to each pixel.
As is well known, an image contains an enormous amount of data. An attempt to process this enormous amount of data will result in a hefty memory volume required for storage of data and in an excessively lengthy processing time. To avoid this, image data is generally compressed through a coding scheme, so that data communication and storage of data can be conducted with a reduced amount of data. Since the black-and-white-multi-level images and the color-multi-level images have a large number of bits per pixel, a coding scheme for effective coding and effective compression is required for these images.
There are two types of image coding schemes for coding and compressing the black-and-white-multi-level images. One of these is a method which treats a plurality of bits per pixel as one unit of data as in accordance with the JPEG. The other is a method which extracts a bit of the same order from a black-and-white-multi-level image for each pixel to create bit planes and applies a binary coding scheme to each bit plane to encode and compress the original image. The latter method is called a bit-plane coding method. In this bit-plane coding method, the MH (modified Huffman) method, the MR (modified Read) method, the MMR (modified modified-Read) method, the JBIG (Joint Bi-level Image coding expert Group) method, etc., is used as the binary coding scheme.
FIG. 1 is an illustrative drawing showing a relation between the bit planes and the original image. As shown in FIG. 1, when a multi-level image comprising eight bits per pixel is to be coded by the bit-plane coding method, for example, the eighth bits of the original image are extracted to form a bit plane BP8, the seventh bits of the original image are extracted to form a bit plane BP7, and so on.
Each of the bit planes BP8 through BP1 created in this manner can be treated as binary image data. Recently, the JBIG method has been attracting attention as an highly efficient compression method for binary image data.
The JBIG method is based on an assumption that an image can be modeled by the Markov process, and encodes a current pixel according to a state thereof. Namely, a plurality of reference pixels surrounding the current pixel are extracted by using a model template, and the state of the current pixel is predicted based on the bit pattern of the reference pixels. Then, the QM-coder coding process is applied based on the predicted probability to code and compress the binary image data.
In the following, arithmetic codes forming a foundation of the QM-coder coding method will be described.
An arithmetic code of a given symbol sequence is obtained by determining a range corresponding to the given symbol sequence within a range 0, 1) and by representing a point in the range as a binary decimal. The determination of the range is made by starting from the range 0, 1) and recursively dividing a range based on a probability of occurrence of each symbol.
FIG. 2 is an illustrative drawing for explaining a binary arithmetic coding method. FIG. 2 shows a procedure in which a symbol sequence "0100" is coded.
In FIG. 2, when a first symbol "0" of the symbol sequence "0100" is to be coded, the range 0, 1) is divided into two ranges A(0) and A(1) in proportion to probabilities of occurrence of symbols "0" and "1". Since the first symbol is "0", the range A(0) is selected. When a second symbol "1" of the symbol sequence "0100" is to be coded, the range A(0) is divided into two ranges A(00) and A(01) in proportion to conditional probabilities of occurrence of the symbol "0" and "1" under the condition that the preceding symbol is "0". Since the first two symbols are "01", the range A(01) is selected. The division of a range and the selection of a divided range are carried out for the coding of the symbol sequence.
The arithmetic coding method described here is a non-block coding method, and is suitable when the probabilities of occurrence of symbols (black or white) are dependent on the conditions (contexts) as in a predicting coding method. Also, the arithmetic coding method needs a relatively small amount of hardware for the coding unit and the memory unit, compared to the run-length coding method such as the MH coding method. Furthermore, the arithmetic coding method can achieve a high efficiency in the coding, and can be relatively easily implemented.
The QM-coder coding method mentioned above employs the arithmetic coding method with a smaller amount of hardware at a higher processing speed. In general, image data is not directly subjected to the arithmetic coding method. Namely, a decision as to whether each pixel of the image data is a superior symbol or an inferior symbol is made in advance based on the predicting coding process. The inferior symbol is a symbol having the lowest probability of occurrence in a given context, and the superior symbol is a symbol having the highest probability of occurrence in the given context. Therefore, a decision as to which one of the superior symbol and the inferior symbol is a white pixel or a black pixel is statistically made based on the context.
In the following, a coding/decoding algorithm of the QM-coder coding method will be described.
The coding starts with the range 0, 1) (i.e., a range greater than or equal to 0 and smaller than 1). The range has a length A, and the inferior symbol has a probability Qe of the occurrence thereof under a given Markov state (i.e., Markov state 0 for the initial condition). Ranges obtained by dividing the range are given as: EQU a=A.multidot.(1-Qe) (1) EQU b=A.multidot.Qe (2)
where a is a length of a range corresponding to the superior symbol and b is a length of a range corresponding to the inferior symbol. If the first symbol is the superior symbol (e.g., 0), the range a is newly assigned as the range A. If the first symbol is the inferior symbol (e.g., 1), the range b is assigned as the range A. Then, further divisions are made for the following symbols. For this process, a coding table is provided to store relations between the probability Qe and a state number indicating a Markov state and to store information on state transitions at a time of a renormalization process (which will be described later).
Multiplication operations required in the equations (1) and (2) are disadvantageous in terms of the hardware size and the processing speed. Also, if a code sequence having an infinite length is to be coded, infinite-size operation registers are necessary for the calculation of infinitesimally small ranges.
To overcome the above-identified problems, the QM-coder coding method manipulates the process such that a newly assigned range A ranges from 0.75 to 1.5 to approximate the range A to 1. Also, the equations (1) and (2) are approximated by: EQU a=A-Qe (3) EQU b=Qe (4)
When A becomes smaller than 0.75, A is bit-shifted to the left such that A becomes greater than or equal to 0.75 and smaller than 1.5. This is the renormalization process. The renormalization process makes it possible to use a subtraction operation instead of the multiplication operations and to use finite-size operation registers. After the renormalization process, a transition to a next Markov state is made based on the current Markov state and a decision as to the current symbol is the superior symbol or the inferior symbol.
FIG. 3A is a flowchart of a process of coding the superior symbol, and FIG. 3B is a flowchart of a process of coding the inferior symbol. In these figures, C represents a code, and an initial value thereof is zero.
When the superior symbol is to be coded, at a step S101, the code C is not modified.
At a step S102, the range A is updated by subtracting the probability Qe corresponding to the current Markov state from A.
At a step S103, a check is made whether the range A is smaller than 0.75. If it is smaller, the procedure goes to a step S104. Otherwise, the procedure skips the step S104.
At a step S104, the range A and the code C are subjected to the renormalization process, and a state transition is made. If the step S104 is skipped as a result of the check at the step S103, the current Markov state is maintained. This ends the procedure for the coding of the superior symbol.
When the inferior symbol is to be coded, at a step S201, the code C is incremented by (A-Qe).
At a step S202, the range A is updated to the probability Qe.
At a step S203, the range A and the code C are subjected to the renormalization process, and a state transition is made.
The code C thus generated corresponds to a binary decimal value indicating the lowest point within the range. The renormalization process bit-shifts the code C to the left by the same number of digits as for the range A, and a portion of the code C exceeding 1 is output as coded data.
FIG. 3C is a flowchart of a decoding process.
At a step S301, a check is made whether the code C is smaller than (A-Qe). If it is smaller, the procedure goes to a step S302. Otherwise, the procedure goes to a step S306.
At the step S302, it is ascertained that the current pixel to be decoded is a superior pixel.
At a step S303, the range A is updated by decreasing A by the probability Qe corresponding to the current Markov state.
At a step S304, a check is made whether A is smaller than 0.75. If it is smaller, the procedure goes to a step S305. Otherwise, the procedure skips the step S305.
At the step S305, the range A and the code C are subjected to the renormalization process, and a state transition is made. If the step S305 is skipped as a result of the check at the step S304, the current Markov state is maintained. This ends the procedure for the decoding of the current symbol.
At the step S306 which is one of the branches after the check at the S301, it is ascertained that the current pixel is an inferior symbol.
At a step S307, the code C is updated by decreasing the code C by (A-Qe).
At a step S308, the range A is updated to the value of the probability Qe.
At a step S309, the range A and the code C are subjected to the renormalization process, and a state transition is made. This ends the procedure for the decoding of the symbol.
In this manner, when a superior symbol occurs, the code C does not change at the time of coding, so that the chance of the renormalization process being required is low. When an inferior symbol appears, the renormalization process is conducted and the coded data is generated.
Accordingly, a predicting coding method which assigns a symbol of the lowest probability to the inferior symbol enhances the coding efficiency and the processing speed.
FIG. 4 is a block diagram of a coding device which encodes and compresses multi-level-image data by using the JBIG method.
In FIG. 4, the coding device includes an image inputting unit 1, a bit-plane generating unit 2, a bit-plane memory 3, a data-reference unit 4, and a arithmetic coding unit 7. The arithmetic coding unit 7 includes an arithmetic coding engine (unit) 5 and a probability estimating unit 6.
The image inputting unit 1 receives multi-level-image data comprised of eight bits per pixel, for example. The image data is supplied to the bit-plane generating unit 2 from the image inputting unit 1. The bit-plane generating unit 2 expands the multi-level-image data into bit planes, and bit-plane data is stored in the bit-plane memory 3.
The data-reference unit 4 reads data of the current pixel to be coded from the bit-plane memory 3, and supplies the data as current-pixel data DX to the arithmetic coding engine 5. Also, the data-reference unit 4 reads data of a plurality of reference pixels from the bit-plane memory 3 by applying a predetermined template to the current pixel, and supplies the data as reference-pixel data DR to the probability estimating unit 6.
The probability estimating unit 6 determines the context of the current pixel based on the reference-pixel data DR. Then, the probability estimating unit 6 obtains an estimated probability of the superior symbol or the inferior symbol, and generates a symbol type indicating the superior symbol or the inferior symbol as being the symbol of the estimated probability. These results are supplied to the arithmetic coding engine 5.
The arithmetic coding engine 5 carries out the arithmetic coding process described above based on the current-pixel data DX, the estimated probability, and the symbol type. Coded data obtained from the arithmetic coding process is output from the arithmetic coding engine 5. If the renormalization process is conducted during the coding process, the arithmetic coding engine 5 informs the probability estimating unit 6 of this fact. The probability estimating unit 6 operating in synchronism with the renormalization process makes a transition of the context to update the state used for the probability estimation. Also, the probability estimating unit 6 stores 8-bit data including a value of the Markov state for each context (i.e., value of the probability estimation index comprising 7 bits) and 1 bit for indicating the superior symbol as being either black or white.
FIG. 5 is an illustrative drawing showing an example of the template used by the data-reference unit 4. The template of FIG. 5 is a so-called JBIG-default-three-line template used in the JBIG method as a default.
In FIG. 5, the current pixel is indicated by X. By using the template of FIG. 5, 10 reference pixels A through J are extracted, and the 10-bit data of these reference pixels is provided for the probability estimating unit 6 of the arithmetic coding unit 7 as the reference-pixel data DR.
The probability estimating unit 6 stores 8-bit data (i.e., the probability estimation index and the indication of the superior symbol) for each of the 1024 contexts (2.sup.10 contexts).
When multi-level-image data of natural images are coded, use of the gray code as a representation of a gray scale of each pixel is preferable to the use of an ordinary binary number. It is empirically known that the use of the gray code can reduce the entropy of an image in each bit plane.
Accordingly, it is preferable to convert the multi-level-image data into the gray code representation prior to the generation of the bit planes BP1 through BP8. After the conversion, the bit planes BP1 through BP8 are created and subjected to the coding process. In this manner, a compression rate of the coding can often be enhanced.
Another method for enhancing the compression rate of the coding is disclosed in Japanese Patent Laid-open Application No. 5-300382. In this method, the reference pixels are extracted from the bit plane of the current pixel and other bit planes as well.
Compared to the use of the gray code prior to the generation of the bit planes, however, this method does not bring about an increase in coding efficiency.
In order to boost the coding efficiency of this method, the reference pixels may be distributed to a larger number of bit planes. In this case, however, the reference pixels are extracted from a large number of bit planes with an increased overhead of the data transfer process for the extraction of the reference pixels. This results in a slow down of the coding processing speed.
Accordingly, there is a need for a bit-plane-coding device which has an enhanced coding efficiency with as small a reduction in the coding processing speed as possible.